/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
// 反转链表
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
// 使用递归函数实现
    ListNode* reverseList(ListNode* head) {
        // 确定边界条件
        if(head==nullptr||head->next==nullptr)return head;
        // 缓存最后一个节点地址
        ListNode *tail=head->next;
        // 递归
        ListNode *new_head = reverseList(head->next);
        // 将头节点地址插入最后一个节点地址后面
        head->next=tail->next;
        tail->next=head;
        return new_head;
    }
};